//1702.修改后的最大二进制字符串
//https://leetcode.cn/problems/maximum-binary-string-after-change/?envType=daily-question&envId=2024-04-10
class Solution {
public:
    //首先00我们一定可以变成10
    //其次 00001 我们可以通过方式2 将1推到最高位 10000
    //也就是说，我们可以在字符串中  碰到00就使用方式1
    //碰到101这样的 就在后面找0 找到0后 通过方式2 一定可以推到当前0后面
    //例如101110 可以变成100111 即110111
    //字符串前面一定是调整好的 不需要调整
    string maximumBinaryString(string binary) {
        int n = binary.size();
        for(int i = 0,j = 0;i<n;++i)
        {
            //如果当前位是0则需要在后面找1
            //如果j小于等于i则需要到i之后
            //否则就在i之后开始找0并推到当前0后面
            if(binary[i]=='0')
            {
                while(j<=i || (j<n&&binary[j]=='1')) ++j;
                if(j < n)
                {
                    //首先将j位置置为1(因为将0推走了)
                    binary[j] = '1';
                    binary[i] = '1';
                    binary[i+1] = '0'; //如果j没有到最后 则至少j在i后面 i+1一定在合法区间
                }
            }
        }
        return binary;
    }
};